package com.algorithm.ch1.yjx.array;

import java.util.Arrays;

/**
 * @author yuanjianxin
 * @date 2018/8/10 17:17
 */
public class    SingleNumber {

    public static void main(String[] args) {
        int[] nums = {4, 3, 4, 1, 2, 1, 2};
//        System.out.println(singleNumber(nums));
        System.out.println(optimumSolution(nums));
    }


    /**
     * 时间复杂度O(nlog(n))
     *
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int index = 0;
        for (int i = 1; i < nums.length; ) {
            if (nums[i] == nums[index]) {
                index = i + 1;
                i += 2;
            } else {
                break;
            }
        }
        return nums[index];
    }

    /**
     * 最优解 时间复杂度O(n)
     * a^a=0;
     *
     * @param arr
     * @return
     */
    public static int optimumSolution(int[] arr) {
        //运行最快 需要O(1)的额外空间
        int result = 0;
        for (int i : arr) {
            result ^= i;
        }
        return result;

        //不需要额外空间
//        for (int i = 1; i < arr.length; i++) {
//            arr[0] ^= arr[i];
//        }
//        return arr[0];
    }
}
